package Kruskal算法;

import java.util.*;

/**
 * @author: AirMan
 * @date: 2025/6/7 15:23
 * @description:
 * 题目描述：
 * 在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
 * 不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来。
 * 给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
 * 输入描述：
 * 第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
 * 接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
 * 输出描述：
 * 输出联通所有岛屿的最小路径总距离
 */
public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt();
        int e = sc.nextInt();

        // 邻接矩阵存放
        int[][] graph = new int[v + 1][v + 1];
        for (int i = 0; i <= v; i++) {
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int value = sc.nextInt();
            graph[v1][v2] = value;
            graph[v2][v1] = value;
        }

        // 收集边的信息
        List<Edge> edges = new ArrayList<>();
        for (int i = 1; i <= v; i++) {
            for (int j = i; j <= v; j++) {
                if (graph[i][j] != Integer.MAX_VALUE) {
                    edges.add(new Edge(i, j, graph[i][j]));
                }
            }
        }

        // 按照边的升序进行排序
        edges.sort(Comparator.comparingInt(edge -> edge.value));

        // 从小到大进行选取，如果边的两个端点不在同一个集合中，那么就选取这一条边
        init(v); // 初始化并查集
        int result = 0; // 记录权重
        for (Edge edge : edges) {
            int v1 = find(edge.v1);
            int v2 = find(edge.v2);
            if (v1 == v2) continue;
            // 选取该边
            union(v1, v2);
            result += edge.value;
            // 输出选取的边
            System.out.println(edge.v1 + " <--> " + edge.v2);
        }
        System.out.println("总权重：" + result);
    }

    public static int[] father;
    public static int[] rank;

    public static void init(int n) {
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
        rank = new int[n + 1];
    }

    public static int find(int u) {
        if (u != father[u]) {
            u = find(father[u]);
        }
        return father[u];
    }

    public static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (rank[u] < rank[v]) {
            father[u] = v;
        } else if (rank[u] > rank[v]) {
            father[v] = u;
        } else {
            father[v] = u;
            rank[u]++;
        }
    }
}

class Edge {
    int v1;
    int v2;
    int value;

    public Edge(int v1, int v2, int value) {
        this.v1 = v1;
        this.v2 = v2;
        this.value = value;
    }
}